%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A connected graph $G$.
\Ensure A spanning tree of $G$.
%%
%% algorithm body
\State $T \gets G$
\While{\rm $T$ is not a tree}
  \State $e \gets$ random edge of $T$
  \If{\rm $T - e$ is connected}
    \State $T \gets T - e$
  \EndIf
\EndWhile
\State \Return $T$
\end{algorithmic}
